package leetcode.search;

import java.util.Stack;

/**
 岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。
 你可以假设grid 的四个边缘都被 0（代表水）包围着。

 岛屿的面积是岛上值为 1 的单元格的数目。

 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

 */
public class MaxAreaOfIsland695 {

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int area = Integer.MIN_VALUE;

        if(m==0||n==0) return 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                area = Math.max(area,dfs(grid,i,j));
            }
        }
        return  area;
    }

    public static void main(String[] args) {
        int [][]arr = new int[][]{{0,1},{1,1}};
        int i = new MaxAreaOfIsland695().maxAreaOfIslandStack(arr);
        System.out.println("res: "+i);
    }

    public int maxAreaOfIslandStack(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int area = 0;
        int localArea;

        if(m==0||n==0) return 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1){
                    Stack<int[]> stack = new Stack<>();
                    stack.push(new int[]{i,j});
                    grid[i][j] = 0;

                    localArea = 1;

                    while (!stack.isEmpty()){
                        int[] point = stack.pop();
                        int x = point[0];
                        int y = point[1];

                        if(x-1>=0 && grid[x-1][y]==1){//上
                            int []up  = new int[]{x-1,y};
                            localArea++;
                            stack.push(up);
                            grid[x-1][y]=0;
                        }
                        if(x+1<m && grid[x+1][y]==1){//下
                            int []down  = new int[]{x+1,y};
                            localArea++;
                            stack.push(down);
                            grid[x+1][y]=0;
                        }
                        if(y+1<n && grid[x][y+1]==1){//右
                            int []right  = new int[]{x,y+1};
                            localArea++;
                            stack.push(right);
                            grid[x][y+1]=0;
                        }
                        if(y-1>=0 && grid[x][y-1]==1){//左
                            int []left  = new int[]{x,y-1};
                            localArea++;
                            stack.push(left);
                            grid[x][y-1]=0;
                        }
                    }
                    area = Math.max(area,localArea);
                }
            }
        }
        return  area;
    }

    private  int  dfs(int[][]grid,int i,int j){
        int m = grid.length;
        int n = grid[0].length;

        if(i>=m || i<0
                || j>=n || j<0 //越界
                || grid[i][j]==0)
            return 0;

        grid[i][j] = 0;

        return 1+dfs(grid,i-1,j)+//上
                 dfs(grid,i+1,j)+//下
                dfs(grid,i,j+1)+//右
                dfs(grid,i,j-1);//左

    }
}